package sysu.el.graph.undi.algor;

import java.util.ArrayList;

import sysu.el.array.BoolArray;
import sysu.el.array.ints.ArrStackInt;
import sysu.el.graph.GraphConstants;
import sysu.el.graph.undi.UndiGT;

public class RingSearching {

	public RingSearching(UndiGT g){
		graph = g;
		curNodeStack = new ArrStackInt(g.getNodeNum() + 1);
		adjNodeEn = new ArrStackInt(g.getNodeNum() + 1);	
		inStackNode = new BoolArray(g.getNodeNum() + 1);
	}

	/**
	 * Referenced Data
	 * Read-Only
	 */
	UndiGT graph;
	
	/**
	 * Algorithm Data
	 */
	ArrStackInt curNodeStack;
	ArrStackInt adjNodeEn;
	BoolArray inStackNode;
	int depth;

	public void initStack(){
		curNodeStack.reset();
		adjNodeEn.reset();
		inStackNode.reset();
		depth = 0;
	}

	public void push(int node){
		curNodeStack.push(node);
		adjNodeEn.push(graph.getDegree(node)-1);
		/** It is a clever trick, it should be true, however, we need it 
		 * to tag ring end point, now 
		 * 		inStackNode.setUnVisited(node)
		 * */
		inStackNode.setVisited(node);
		depth ++;
	}

	public void pop(){
		int cur = curNodeStack.pop();
		adjNodeEn.pop();
		inStackNode.setUnvisited(cur);
		depth --;
	}

	/**
	 * Must Use the DFS
	 * @param g
	 * @param node
	 * @param maxgetNodeNum() refers the maximum node number in the ring
	 * @param Paths
	 */
	
	public void searchRings1(int node, int maxNodeNum,
			ArrayList<int[]> paths){

		this.initStack();
		this.push(node);
		do{
			int cur = curNodeStack.top();
			if (depth < maxNodeNum){
				 //	if (depth < maxgetNodeNum())
				// Notice: next != 0 is wrong here for g.getDegree(node) maybe zero
				// int next = pointEn.setTop(pointEn.setTop -1)
				int next = adjNodeEn.top();
				if (next >= 0){
					cur = graph.getList(cur)[next];
					adjNodeEn.setTop(next-1);
					if (inStackNode.isUnvisited(cur))
						this.push(cur);
					else if ((cur == node) && (depth > 2)){
						curNodeStack.push(cur);
						int[] path = curNodeStack.toArray();
						paths.add(path);
						curNodeStack.pop();
					}
					continue;
				}
			}else if (graph.getW(cur, node) != GraphConstants.NULL_EDGE){
				this.push(node);
				continue;
			}
			this.pop();
		}while (!curNodeStack.isEmpty());
	}

	public ArrayList<int[]> searchRings(int node, int maxLen){
		ArrayList<int[]> rings = new ArrayList<int[]>(16);
		searchRings1(node, maxLen, rings);
		return rings;
	}
}
